package TP5.ejercicio2;

import TP2.sorters.AbstractSorter;
import anaydis.sort.SorterType;

import java.util.Comparator;
import java.util.List;
import java.util.Locale;

/**
 * Created by IntelliJ IDEA.
 * User: pc
 * Date: 18/11/11
 * Time: 21:59
 * To change this template use File | Settings | File Templates.
 */
public class HeapSorter extends AbstractSorter{

    public HeapSorter() {
            super(SorterType.HEAP);
    }

        public <T> void sort(Comparator<T> comparator, List<T> list){
            for (int i = list.size() / 2; i >= 0; i--)
                subSort(comparator, list, i, list.size());
            for (int i = list.size() - 1; i > 0; i--) {
                swap(list, 0, i);
                subSort(comparator, list, 0, i);
            }
        }

        public <T> void sort(Locale locale, Comparator<T> comparator, List<T> list) {
            for (int i = list.size() / 2; i >= 0; i--)
                subSort(locale, comparator, list, i, list.size());
            for (int i = list.size() - 1; i > 0; i--) {
                swap(list, 0, i);
                subSort(locale, comparator, list, 0, i);
            }
        }

        private static int leftChild(int i) {
            return 2*i+1;
        }

        private <T> void subSort(Comparator<T> comparator, List<T> list, int i, int n) {
            int child;
            for (list.get(i); leftChild(i) < n; i = child) {
                child = leftChild(i);
                if (child != n - 1 && greater(comparator, list, child+1, (child)))
                    child++;
                if (greater(comparator, list, child, i))
                    swap(list, i, child);
                else
                    break;
            }
        }

        private <T> void subSort(Locale loc, Comparator<T> comparator, List<T> list, int i, int n) {
            int child;
            for (list.get(i); leftChild(i) < n; i = child) {
                child = leftChild(i);
                if (child != n - 1 && greater(loc, comparator, list, child + 1, (child)))
                    child++;
                if (greater(loc, comparator, list, child, i))
                    swap(list, i, child);
                else
                    break;
            }
        }



}
